The present invention relates to three dimensional graphics and volumetric imaging and more particularly to method and apparatus for real-time rendering of high resolution volumetric images.
Image rendering is the process of converting complex information to a format which is amenable to human understanding while maintaining the integrity and accuracy of the information. Volumetric data, which consists of information relating to three-dimensional phenomena, is one species of complex information which can benefit from improved image rendering techniques. The process of analyzing volumetric data to determine, from a given view point, which portions of a volume are visible is commonly referred to as volume viewing. Traditional methods of volume viewing operate by scanning through data points in a strict sequential manner in order to achieve removal of hidden lines and surfaces. The need to model objects in two-dimensional (2-D) and three-dimensional (3-D) space is manifest, and the advantages of doing so using computer graphic systems is clear.
Presently, a variety of computer graphic systems are known, and for the greater part, have been characterized in terms of the data they manipulate. For example, there are systems which manipulate data represented on the continuous object (geometric) space R.sup.3, those which operate on the discrete pixel-image plane Z.sup.2, and those which work on the discrete voxel-image space Z.sup.3.
A great deal of energy and effort has been expended on systems using the former two approaches. An example of a system based on such techniques is a typical 2-D computer graphics raster-display system. Therein, 3-D graphics information is stored in a "graphic display list" as a structured collection of 3-D geometric primitives which represent a model of the scene or object to be displayed. A graphics/geometry processor creates the desired image on the basis of the information stored in the display list. The display list images are transformed, shaded, colored, mapped onto the display screen, scan-converted into an unstructured matrix of pixels, and stored within a 2-D frame buffer. A video processor then refreshes the display screen from the 2-D frame buffer. Each change in the scene requires the graphics processor to repeatedly perform a complete computationally-intense pixel-generation process. This repeated processing causes both computation and buffer contention problems which slow down the operation of the graphics system. This phenomenon is crucial especially in real-time systems such as animation and simulation.
As a result of recent developments and research, graphics/geometry processors are now commercially available which speed-up the above-described computationally-intense process. In conjunction with these geometry processors, or as an alternative, parallel processors which exploit the parallel nature of images and picture handling have been utilized.
As a result of advances in computational science and technology, it has become quite conventional to use three-dimensional computer graphic systems having surface and solid modelling capabilities. As with other types of graphics systems, these computer graphic systems are characterized by the fact that the 3-D object or scene is represented by a geometric model in 3-D continuous geometric space, R.sup.3. Such 3-D geometric models are typically constructed from continuous 3-D geometric representations, such as 3-D straight line segments, planar polygons, polyhedra, circles, cubic polynomial curves, surfaces, and volumes, and quadratic objects such as spheres, cones, and cylinders. These 3-D geometric representations are used to model various parts of an object, and are expressed in the form of mathematical functions evaluated over particular coordinate values in continuous R.sup.3 space. Typically, the 3-D geometric representations of the 3-D geometric model are stored in a graphic display list. Once modelled using continuous 3-D geometric representations, the object can be displayed along a particular viewing direction by repeatedly scan-converting the graphic display list.
The above-described 3-D geometric-based graphic systems have significant shortcomings. For example, when viewing the 3-D geometric model of the 3-D object, only the surfaces visible to an observer along a particular viewing direction should be displayed. However, to ensure this, the hidden surfaces must be detected using surface detection algorithms, and removed by a computationally intense process referred to as "hidden surface removal". These systems also require that even for the smallest display modification, for example, a change in viewing direction, the graphic display list must be manipulated and repeatedly scan-converted, which is both time consuming and computationally intense.
Another shortcoming of the 3-D geometric-based graphic system is that the projection, rendering and manipulation of a 2-D view of the 3-D geometric model is dependent on the complexity of the scene being displayed. In addition, in some applications such as medical imaging, biology, geology and 3-D image processing, the data is already in voxel-based form and no geometric information is available.
As an alternative to 3-D geometric-based systems, several 3-D voxel-image space systems have been developed. In general, these voxel-image space systems are based on the concept that a 3-D continuous object or scene is discretized, sampled, and stored in a large 3-D Cubic Frame Buffer (CFB) memory comprising unit cubic cells called volume elements or "voxels". Three-dimensional objects are digitized and a regularly spaced 3-D matrix array of values is obtained and stored in the Cubic Frame Buffer. The 3-D array of voxels in the Cubic Frame Buffer may be loaded with experimental data obtained, for example, by a 3-D scanner such as a CAT or MRI medical scanner, or by a super computer running a simulation such as a computation in fluid dynamics, or from a voxel data base. Alternatively, the digitization is performed by scan-converting a 3-D geometric model. Both experimental and synthetic samples yield a cellular tessellation of the original volume, and the resulting cellular cubic memory provides a real yet discrete model of the 3-D scene or object. Consequently, the voxel representation, which is fundamental to all 3-D voxel-based systems, is very effective for the traditional applications employing empirical 3-D voxel imagery, such as medicine (e.g. computed tomography and ultrasounding), geology, biology, and 3-D image processing (e.g. time varying 2-D images).
The advantages of using voxel representations of objects and scenes are numerous. The projection of voxel-based images along a view direction displays only the visible surfaces and implicitly ignores the hidden surfaces of the 3-D voxel-images. Therefore, separate hidden surface removal methods need not be employed. Also, for every small modification, there is no need to repeatedly scan-convert and manipulate graphic display lists as required in 3-D geometric-based graphics systems. Rather, a change can be made directly to the Cubic Frame Buffer images (i.e. objects can be directly edited by deleting, masking out, or adding voxels with minimal computational effort). Therefore, when using a voxel-based system, projection, rendering and manipulation are independent of the scene complexity, and it is normally unnecessary to employ conventional display lists, repeated scan-conversions, and computationally intense hidden surface removal or surface detection algorithms.
To date, there have been several proposals for 3-D voxel-based graphics systems, all of which have one thing in common, namely, the utilization of high performance multi-processing architectures in order to process the enormous amount of voxel-represented data in the cellular cubic memory. These prior art voxel based systems have substantial shortcomings and drawbacks in that they cannot provide real-time manipulation of data and rendering of an object from an arbitrary viewing direction.
It is therefore an object of the present invention to provide a method and apparatus which is more efficient and, provides better resolution than existing 3-D voxel based graphics systems.
Other and further objects will be made known to the artisan as a result of the present disclosure and it is intended to include all such objects which are realized as a result of the disclosed invention.